package 字节跳动手撕.A;

import java.util.List;

public class ListNode {
    int val;
    ListNode next;

    public ListNode(int val) {
        this.val = val;
    }
    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || k == 1) {
            return head;
        }
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode end = dummy;
        //end 指向的是虚拟节点
        while (end.next != null) {
            for (int i = 0; i < k&&end!=null; i++) {
                end = end.next;
            }
            //不足k组的时候 直接结束
            if (end == null) {
                break;
            }
            ListNode start = pre.next;

            ListNode next = end.next;
            //将后面的节点断开
            end.next = null;

            //反转完成的
            ListNode fanzhuan = reverseNode(start);

            pre.next = fanzhuan;

            //原来第一个到了末尾 接上去
            start.next = next;

            pre = start;

            end = pre;
        }
        return dummy.next;
    }

    // public ListNode reverseKGroup(ListNode head, int k) {
    //        if (head == null || k == 1) {
    //            return head;
    //        }
    //        ListNode dummy= new ListNode(-1);
    //
    //        dummy.next=head;
    //        ListNode pre=dummy;
    //        ListNode end=dummy;
    //
    //         while (end.next != null) {
    //             for (int i = 0; i < k&& end!=null; i++) {
    //                 end=end.next;
    //             }
    //             if (end==null) {
    //                 //小于k个不用反转
    //                 break;
    //             }
    //             //将k个一组分开 进行反转 反转结束之后再拼接和移动
    //             ListNode start=pre.next;
    //             //保存下一个
    //             ListNode next=end.next;
    //             //断开
    //             end.next=null;
    //                    //反转完成之后 pre.next指向反转之后的
    //             pre.next=reverseNode(start);
    //
    //             //start 变成末尾节点了 指向next
    //             start.next=next;
    //
    //             //pre指向前面节点
    //             pre=start;
    //
    //             //end和pre都是再下一次反转的前一个节点
    //             end=pre;
    //         }
    //         return dummy.next;
    //    }
    //   ListNode pre=null;
    //       ListNode cur=head;
    //       while (cur!=null){
    //           ListNode next=cur.next;
    //           cur.next=pre;
    //           pre=cur;
    //           cur=next;
    //       }
    //       return pre;
     //反转单链表
    private ListNode reverseNode(ListNode head) {
       //反转单链表
        ListNode pre =null;
        ListNode cur=head;
        while (cur!=null){
            ListNode curNextTemp=cur.next;
            cur.next=pre;
            pre=cur;
            cur=curNextTemp;
        }
        //cur等于null的时候,pre指向链表的最后一个节点
        return pre;
    }
     //最长递增自学列
    public int lengthOfLIS(int[] nums) {
        int n=nums.length;
        int dp[] =new int[n];
        int maxLen=0;
        for (int i = 0; i < n; i++) {
            dp[i]=1;
            for (int j = 0; j <i; j++) {
                if(nums[i]>nums[j]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                    maxLen=Math.max(maxLen,dp[i]);
                }
            }
        }
        return maxLen;
    }
    //
    public void reorderList(ListNode head) {

    }
}
